//
// Created by 123 on 2024/3/11.
//
#include <iostream>
#include <stack>

using namespace std;

typedef struct BiTNode {
    int data;
    BiTNode *lchild;
    BiTNode *rchild;
} BiTNode, *BiTree;

void show(BiTNode *node);

void level_show(BiTNode *node);

BiTNode *init_Node() {
    BiTNode *node = (BiTNode *) malloc(sizeof(BiTNode));
    node->lchild = NULL;
    node->rchild = NULL;
    return node;
}


//先序遍历非递归版
void pre_use_stack(BiTNode *node);

//中序遍历非递归版
void in_use_stack(BiTNode *node);

//后序遍历非递归版
void post_use_stack(BiTNode *node);


int main() {
    BiTree tree = init_Node();
    tree->data = 1;
    BiTNode *n2 = init_Node();
    n2->data = 2;
    BiTNode *n3 = init_Node();
    n3->data = 3;
    BiTNode *n4 = init_Node();
    n4->data = 4;
    BiTNode *n5 = init_Node();
    n5->data = 5;
    BiTNode *n6 = init_Node();
    n6->data = 6;
    BiTNode *n7 = init_Node();
    n7->data = 7;
    BiTNode *n8 = init_Node();
    n8->data = 8;
    BiTNode *n9 = init_Node();
    n9->data = 9;

    tree->lchild = n2;
    tree->rchild = n3;

    n2->lchild = n4;
    n2->rchild = n5;

    n3->lchild = n6;
    n3->rchild = n7;

    n4->lchild = n8;
    n4->rchild = n9;
    cout<<"前序遍历"<<endl;
    pre_use_stack(tree);
    cout<<"中序遍历"<<endl;
    in_use_stack(tree);
    cout<<"后序遍历"<<endl;
    post_use_stack(tree);

}

void visit(BiTNode *node) {
    cout << node->data << "   ";
}

/**
  * 先弹栈，
  * 若有右，压入右
  * 若有左，压入左
  *
  * @param node
  */
//先序遍历非递归版
void pre_use_stack(BiTNode *node){
    stack<BiTNode *> sta;
    sta.push(node);
    BiTNode *p;
    while (!sta.empty()){
        p=sta.top();
        visit(p);
        sta.pop();
        if(p->rchild!=NULL)
            sta.push(p->rchild);
        if(p->lchild!=NULL)
            sta.push(p->lchild);
    }
    cout<<endl;
}

/**
 * 左边持续压栈，直到没有左子树了，
 * 输出当前节点，当前节点指向右节点
 * 继续上述操作
 * @param node
 */
//中序遍历非递归版
void in_use_stack(BiTNode *node) {
    stack<BiTNode *> sta;
    BiTNode *p=node;
    while (p!=NULL||!sta.empty()){
        if(p!=NULL){
            sta.push(p);
            p=p->lchild;
        }else{
            p=sta.top();
            sta.pop();
            visit(p);
            p=p->rchild;
        }
    }
    cout<<endl;
}
/**
  * 弹栈输出
  * 若有左，压入左
  * 若有右，压入右
  * 得到中右左的输出顺序
  * 用栈反转，得到左右中的输出顺序，即后续遍历
  *
  * @param node
  */
//后序遍历非递归版
void post_use_stack(BiTNode *node){
    stack<BiTNode *> sta1;
    stack<BiTNode *> ans;
    BiTNode *p=node;
    sta1.push(p);
    while (!sta1.empty()){
        p=sta1.top();
        ans.push(p);
        sta1.pop();
        if(p->lchild!=NULL)
            sta1.push(p->lchild);
        if(p->rchild!=NULL)
            sta1.push(p->rchild);
    }
    while (ans.size()!=0){
        visit(ans.top());
        ans.pop();
    }
    cout<<endl;
}
